package 位运算;

import org.junit.Test;

public class countBits338 {

    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        int index = 0;
        for (int i = 0; i <= n; i++) {
            ans[index++] = Integer.bitCount(i);
        }
        return ans;
    }

    /**
     * 使用的Brian Kernighan 算法
     *
     * @param n
     * @return
     */
    public int[] countBits2(int n) {
        int[] ans = new int[n + 1];
        int index = 0;
        for (int i = 0; i <= n; i++) {
            ans[index++] = check(i);
        }
        return ans;
    }

    private int check(int i) {
        int res = 0;
        while (i != 0) {
            i = i & (i - 1);
            res++;
        }
        return res;
    }

    @Test
    public void test() {
        int[] ints = countBits2(5);
        for (int i : ints) {
            System.out.print(i);
        }
    }
}
